1. Field of the Invention
The present invention relates in general to a revenue management system (also referred to as "yield management" system) for allocating resources or inventory in which a multidimensional lookup table of threshold values is employed for each resource as the control logic for dynamically adjusting the acceptable revenue value for the resources as a function of two or more variables.
2. Description of the Prior Art
Revenue management systems seek to maximize the revenue generated from a fixed service or productive capacity by selectively accepting or denying requests for capacity. For example, in airlines a network of flights with a set of seats are available for sale on a given day, and customers request seats in advance of travel for various itineraries on the network. Based on the current reservations already accepted for each flight (alternatively, the remaining capacity available), the time remaining in the sales horizon and forecasts of future demand for itineraries, airlines must decide which itineraries and fare classes to accept and which to deny (or close out).
These decisions are very detailed and complicated to make because future demand is typically highly uncertain and one must evaluate complex tradeoffs between the current and future value of capacity. Therefore, revenue management decisions are typically made or guided by a software system (revenue management system) that incorporates a variety of advanced statistical and mathematical methods. Revenue management is widely used in the airline, hotel and car-rental industries and is spreading to the energy, natural gas pipelines, broadcasting, shipping, sports, entertainment facilities, manufacturing, equipment leasing and cargo industries. Indeed, the practice is applicable in any industry that has limited short-term capacity flexibility and variable demand.
A variety of mathematical models have been proposed to solve the problem of which requests to accept or deny based on current capacity and forecasts of future demand. However, regardless of the mathematical model and assumptions used, revenue management software systems ultimately need an internal control logic to implement the accept/deny recommendations. To date, two control schemes have been developed to implement accept/deny decisions: nested capacity allocation and static-bid prices.
The oldest and most widespread approach to implementing accept/deny decisions is to use nested capacity allocations (also called "booking limits") on the various classes and rates for the capacity. This is the approach used in the early work of Littlewood (1972) on discount fare class allocation. It was popularized in the academic literature by Belobaba (1987, 1989). This is the approach used in many of the older commercial revenue management systems.
One example of a nested capacity allocation scheme is known as Single-resource Nested Allocations. This approach was originally developed to allocate capacity of a single resource, for example a single flight leg, to one of n possible demand classes (fare-classes in airline industry). The control logic works as follows:
Let c be the total capacity. Let the net revenues of the n demand types be denoted f.sub.i and assume without loss of generality that these demand classes are indexed so that f.sub.1 &gt;f.sub.2 &gt;Y&gt;f.sub.n. A so-called nested allocation logic specifies values (protection levels) x.sub.1, x.sub.2, Y, x.sub.n that satisfy EQU 0.ltoreq.x.sub.n.ltoreq.x .sub.n-1.ltoreq.Y.ltoreq.x.sub.n =c.
Let y denote the remaining capacity. The logic is to accept demand class i if and only if EQU y&gt;x.sub.i i=1,Y,n
That is, demand class i is accepted if the remaining capacity exceeds the protection level, x.sub.i, for that class. An alternative and more popular method to implement this same logic is to define a set of booking limits, b.sub.i, using EQU b.sub.i =cBx.sub.i
Let r denote the number of reservations on hand (r=c-y). In this case, the logic is to accept a request from demand type i if and only if EQU r&lt;b.sub.i
That is, accept demand class i if and only if the number of reservations on hand is less than the booking limit for demand class i. The maximum available capacity for any class i is usually refelTed to as the authorization level and is defined by EQU a.sub.i =max{b.sub.i Br,0}
These are the control logic schemes described in Belobaba (1987, 1989) and Brumelle et al. (1990, 1993) and elsewhere. Belobaba (1987, 1988) describes some approximate methods for setting allocation parameters while Brumelle et al. (1990, 1993) describe exact algorithms for computing the parameters.
Whatever method is used to compute the parameter values, the nested allocation structure has some distinct advantages. Namely, it has the desirable feature that a small number of control parameters (n booking limits or protection levels) can be calculated once by an optimization module. Then, the accept/deny decisions dynamically adjust as available capacity changes. That is, as more capacity is sold, more demand classes are "closed out" as booking limits are reached. Alternatively, when customers cancel, more capacity becomes available and some demand classes may "open up" as the available capacity exceeds their booking limits. In this way, the nested allocation structure adjusts to the evolving capacity conditions.
While the nested allocation scheme works well for a single resource, extending it to allocate capacity for multiple resources (legs of a flight network for example) is somewhat problematic. For example, it is not clear how to rank demand class that use different resources, so the nested structure becomes difficult to apply. Also, if allocations are defined for all revenue values and every combination of resources, the number of allocation values required becomes too large for practical implementation in a reservation system.
To avoid this large number of allocation values, most approaches for extending nested allocation control logic to networks involve converting the multiple-resource allocation problem into a collection of single-resource problems and then applying the controls generated by this collection of single-resource allocation problems.
This is accomplished as follows: First, the revenue values for a multiple resource request are adjusted by quantities that reflect the displacement value of the other resources used by the request. These displacement-adjusted fare values are then used to compute nested allocations for each leg. Displacement adjusted values are often clustered into "virtual classes" first to reduce the number of classes involved. This process of creating virtual classes is called indexing by Smith et al. (1992). See Williamson (1992) and Vinod (1990) for further discussion of this approach, which also goes by the name of virtual nesting (Smith et al. 1992).
These displacement-adjusted values have some advantages: They require only a small number of control variables and the nested allocation structure maintains the favorable property of adjusting accept/deny decisions as available capacity changes. They also provide a maximum available capacity for each demand class through the authorization levels. However, the displacement adjustment process and clustering into virtual classes adds a significant amount of complexity to the control logic. This complexity has made their implementation prohibitive for most users of revenue management systems.
An alternative control logic for multiple-resource problems is to use what are called resource bidprices. This idea was first proposed by Simpson (1989) and was extensively investigated in the Ph.D. dissertation of Williamson (1992). See also Cuny (1992) and Phillips (1994). Let m denote the number of resources to allocate. In a bid price control scheme, values (bid prices) .nu..sub.i, i=1, . . . ,m are set for each of the m resources. Suppose a request comes in to purchase a set of resources {i.sub.1, . . . ,i.sub.k }. Then a bid price control would accept the request of net revenue value if and only if EQU f&gt;.nu..sub.1 +Y+.nu..sub.ik
That is, a request is accepted if and only if the fare exceeds the sum of the bid prices of all the capacity units required to satisfy the demand. The interpretation of the values .nu..sub.i is that they represent the threshold value of resource capacity. Again, a variety of optimization methods and approximations have been proposed for determining the bid price parameter values. (See Simpson (1989) and Williamson (1992).)
The advantage of the bid price logic is that it requires very few parameters, one value for each resource, and does not require separate displacement adjustment and indexing steps. The main weakness is that the logic is not dynamic. Specifically, the accept/deny decisions do not change if remaining capacity fluctuates and/or the time remaining in the horizon changes. As a result, the bid price values .nu..sub.i must be updated very frequently (usually by re-forecasting and re-optimizing a mathematical model) to ensure that they track changes in the available capacity among all resources. Ideally, this updating of bid-prices has to be done after each booking or cancellations (or change in the remaining resource) which is prohibitive to do operationally. They also do not provide any indication of the maximum available capacity for a given demand class and cannot be used directly to compute authorization levels.